package com.algorithms.leetcode.LinkList;

import com.algorithms.leetcode.ListNode;

import java.util.List;

/**

 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 k 是一个正整数，它的值小于或等于链表的长度。
 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 * <br>
 */
public class leetcode_25_reverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode dummy=new ListNode(0);
        dummy.next = head;
        //初始化pre和end都指向dummy。
        //pre指每次要翻转的链表的头结点的上一个节点。
        //end指每次要翻转的链表的尾节点
        ListNode prev = dummy;
        ListNode end = dummy;

        while (end != null){
            //找到本次反转子列表的末尾节点
            for(int i = 0; i < k && end != null ;i++){
                end  = end.next;
            }
            //最后一段子节点 不足K个 无需反转
            if(end == null){
                break;
            }
            //本次反转子序列的后一个序列，单独取出来 方便后面重新连接
            ListNode next = end.next;
            //断开当前子序列
            end.next = null;
            //反转子链表
            ListNode start = prev.next;
            //反转列表
            reverseList(start);
            //重新加入列表
            prev.next = end;
            start.next = next;

            //向下移动
            prev = start;
            end = start;
        }
        return dummy.next;
    }

    /**
     * 迭代法
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null){
            ListNode tmp = curr.next;
            //反转
            curr.next = prev;
            //往下移动
            prev = curr;
            curr = tmp;
        }
        return prev;
    }


    /**
     * 递归
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/chao-qiang-gifzhu-ni-li-jie-shi-yong-di-gui-fa-qiu/
     * @param head
     * @return
     */
    public ListNode reverseKGroupV2(ListNode head,int k) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy=new ListNode(0);
        dummy.next = head;
        ListNode end  = dummy;
        //递归之前取出 K 个节点
        for(int i = 0; i < k && end != null ;i++){
            end  = end.next;
        }
        //最后一段子节点 不足K个 无需反转
        if(end == null){
            return head;
        }
        //取出后面的子序列
        ListNode next = end.next;
        end.next = null;
        //反转列表
        reverseList(head);
        head.next = reverseKGroupV2(next,k);
        return end;
    }

    public static void main(String[] args) {
        ListNode one =new ListNode(1);
        ListNode two =new ListNode(2);
        ListNode three =new ListNode(3);
        ListNode four =new ListNode(4);
        ListNode five =new ListNode(5);
        one.next = two;
        two.next = three;
        three.next =four;
        four.next = five;
        ListNode listNode = new leetcode_25_reverseKGroup().reverseKGroupV2(one,2);
        System.out.println(listNode);
    }

}
